package com.gxc.recursion;

/**
 * CC里面有一个土豪很喜欢一位女直播Kiki唱歌，平时就经常给她点赞、送礼、私聊。
 * 最近CC直播平台在举行中秋之星主播唱歌比赛，
 * 假设一开始该女主播的初始人气值为start，能够晋升下一轮人气需要刚好达到end.
 * 土豪给主播增加人气的可以采取的方法有:
 * a点赞 花费 x C币，人气+2
 * b送礼 花费 y C币，人气*2
 * c私聊 花费 z C币，人气-2
 *
 * 其中 end 远大于start且end为偶数，
 * 请写一个程序帮助土豪计算一下，最少花费多少C币就能帮助该主播Kiki将人气刚好达到end，
 * 从而能够晋级下一轮?
 * 输入描述:
 * 第一行输入5个数据，分别为:x y z start end，每项数据以空格分开
 * 其中:0<x，y.z<=10000， 0<start, end<=1000000
 * 输出描述:需要花费的最少C币。
 * 示例1:
 * 输入
 * 3 100 1 2 6
 * 输出
 * 6
 *
 * 解法:
 * 自定义边界
 * a) 递归超过多少步： end 远大于start且end为偶数， end 必定可以有 start*2 + 2+2........... 加2达到，
 * 假设这种事最坏的情况，最优解必定不小于这个加2的次数
 * b) 当人气达到多少时，不再进行递归，人气如果超过end*2,则也不需要递归
 */
public class LeastCost {

    public static void main(String[] args) {
        System.out.println(process(3, 1, 1, 2, 6));
        System.out.println(dp(6, 2, 3, 1, 1));
    }

    public static int process(int x ,int y, int z, int start, int end) {
        return cost(end, start, 0, x, y, z, (end-start)/2*x, end*2);
    }

    /**
     *
     * @param end   目标分数
     * @param cur   当前分数
     * @param cost  当前的花费
     * @param add   人气+2
     * @param multi 人气*2
     * @param minus 人气-2
     * @param maxCost 已知可得的花费边界
     * @param maxEnd  已知可得的分数边界
     * @return
     */
    public static int cost(int end, int cur, int cost,
                           int add, int multi, int minus,
                           int maxCost , int maxEnd) {
        if (cur > maxEnd) return Integer.MAX_VALUE;
        if (cur <0) return Integer.MAX_VALUE;
        if (cost > maxCost) return Integer.MAX_VALUE;

        if (cur == end) return cost;
        //人气+2
        int cost1 = cost(end, cur + 2, cost + add, add, multi, minus, maxCost, maxEnd);
        //人气*2
        int cost2 = cost(end, cur * 2, cost + multi, add, multi, minus, maxCost, maxEnd);
        //人气-2
        int cost3 = cost(end, cur - 2, cost + minus, add, multi, minus, maxCost, maxEnd);

        return Math.min(cost1, Math.min(cost2, cost3));
    }

    /**
     * ???目前有疑问
     * @param end
     * @param start
     * @param add
     * @param multi
     * @param minus
     * @return
     */
    public static int dp(int end, int start,
                         int add, int multi, int minus) {
        int maxCost = (end-start)/2*add;
        int maxEnd = end * 2;
        int[][] dp = new int[maxEnd+1][maxCost+1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                if (i == end) dp[i][j] = j;
                else dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = maxEnd; i >=0 ; i--) {
            for (int j = maxCost; j >=0 ; j--) {
                int cost1 = Integer.MAX_VALUE;
                int cost2 = Integer.MAX_VALUE;
                int cost3 = Integer.MAX_VALUE;
                //人气+2
                if (i-2>=0 && j+add<=maxCost) cost1 = dp[i - 2][j + add];
                //人气*2
                if (((i & 1) == 0) && i/2>=0 && j+multi<=maxCost) cost2 = dp[i / 2][j + multi];
                //人气-2
                if (i+2<=maxEnd && j+minus<=maxCost) cost3 = dp[i + 2][j + minus];

                dp[i][j] = Math.min(cost1, Math.min(cost2, cost3));
            }
        }

        return dp[start][0];
    }

}
